package CommonAlgs.DP;

/**
 * @Author ChanZany
 * @Date 2021/5/14 19:15
 * @Version 1.0
 * 现有若干枚硬币，硬币面值分别为1,5 ,11要凑出价值为w，至少需要多少枚硬币。比如w=15
 * f(n)=1+min{f(n-1),f(n-5),f(n-11)}
 * f(1)=1 f(6)=1+f(5) or 1+f(1)
 */
public class CoinProblem {
    public static void main(String[] args) {
        int v1 = 1, v2 = 5, v3 = 11,target = 15;
        int res = solution(v1, v2, v3, target);
        System.out.println(res);
    }

    private static int solution(int v1, int v2, int v3, int target) {
        int threshold = min(v1, v2, v3);
        if (target < threshold) return 0;
        if (target == threshold) return 1;
        int[] dp = new int[target / threshold+1];
        dp[0]=0;
        int cost;
        for (int i = 1; i < target+1; i++) {
            cost = 99999;
            if (i-v1>=0) cost = Math.min(cost,dp[i-v1]+1);
            if (i-v2>=0) cost = Math.min(cost,dp[i-v2]+1);
            if (i-v3>=0) cost = Math.min(cost,dp[i-v3]+1);
            dp[i] = cost;
        }
        return dp[target];
    }


    private static int min(int v1, int v2, int v3) {
        int tmp = Math.min(v1, v2);
        return Math.min(tmp, v3);
    }



}
